/*
 * >>> reduce(lambda x, y: print(y, 255**y, int(math.log10(255**y))), list(range(10)))
 * 1 255 2
 * 2 65025 4
 * 3 16581375 7
 * 4 4228250625 9
 * 5 1078203909375 12
 * 6 274941996890625 14
 * 7 70110209207109375 16
 * 8 17878103347812890625 19
 * 9 4558916353692287109375 21
 */

const min = Math.min;
const max = Math.max;
const random = Math.random;

enum Role {
  COMPUTER,
  HUMAN
}

class ToolMan {
  x: number;
  y: number;
  z: number; // score

  constructor (x: number, y: number, z: number) {
    this.x = x;
    this.y = y;
    this.z = z;
  }
}

class Zobrist {
  size: number;
  code: number;
  computer: Array<number>;
  human: Array<number>;

  constructor() {
    this.size = 15;
    this.code = random();
    this.computer = new Array<number>();
    this.human = new Array<number>();
    for (let i = 0; i <= 255; i++) {
      this.computer.push(random());
      this.human.push(random());
    }
  }

  go (x: number, y: number, role: Role) : number {
    const idx = this.size * x + y;
    this.code ^= (role == Role.COMPUTER ? this.computer[idx] : this.human[idx]);
    return this.code;
  }
}

class Evaluate {
  // 董红安的评分表
  static mp = {
    '11111 ': 50000,
    '011110': 4320,
    '011100': 720,
    '001110': 720,
    '011010': 720,
    '010110': 720,
    '11110 ': 720,
    '01111 ': 720,
    '11011 ': 720,
    '10111 ': 720,
    '11101 ': 720,
    '001100': 120,
    '001010': 120,
    '010100': 120,
    '000100': 20,
    '001000': 20,
  };

  isend: boolean = false;

  /*
    '连五': '11111'  ,
    '活四': '011110' ,
    '冲四': '-11110' ,
    '活三': '0011100',
    '眠三': '-01110-',
    '活二': '001100' ,
    '眠二': '-00110-',
  */

  setEnd() :Boolean {
    this.isend = true;
    return true;
  }

  slide8(sinjiro: number, cosjiro: number, left: number, right: number) : number {
    // console.log(sinjiro.toString(2), left, right);
    // console.log(cosjiro.toString(2));
    /*
     * 传入: 0 位上为 1 的 8 bit
     * 3 2 1 0 1 2 3 4
     * - - - x - - - -
     */
    let tanjiro = 0;
                   (right >= 4) && ((sinjiro >> (right - 4) & 0b11111  ^ 0b11111 ) == 0b0) && this.setEnd()                                && (tanjiro += 5e4 );
    (left >= 1) && (right >= 4) && ((sinjiro >> (right - 4) & 0b111111 ^ 0b011110) == 0b0) && ((cosjiro >> (right - 4) & 0b111111) == 0b0) && (tanjiro += 4320);
    (left >= 1) && (right >= 4) && ((sinjiro >> (right - 4) & 0b111111 ^ 0b011100) == 0b0) && ((cosjiro >> (right - 4) & 0b111111) == 0b0) && (tanjiro += 720 );
    (left >= 2) && (right >= 3) && ((sinjiro >> (right - 3) & 0b111111 ^ 0b001110) == 0b0) && ((cosjiro >> (right - 3) & 0b111111) == 0b0) && (tanjiro += 720 );
    (left >= 1) && (right >= 4) && ((sinjiro >> (right - 4) & 0b111111 ^ 0b011010) == 0b0) && ((cosjiro >> (right - 4) & 0b111111) == 0b0) && (tanjiro += 720 );
    (left >= 1) && (right >= 4) && ((sinjiro >> (right - 4) & 0b111111 ^ 0b010110) == 0b0) && ((cosjiro >> (right - 4) & 0b111111) == 0b0) && (tanjiro += 720 );
                   (right >= 4) && ((sinjiro >> (right - 4) & 0b11111  ^ 0b11110 ) == 0b0) && ((cosjiro >> (right - 4) & 0b11111 ) == 0b0) && (tanjiro += 720 );
    (left >= 1) && (right >= 3) && ((sinjiro >> (right - 3) & 0b11111  ^ 0b01111 ) == 0b0) && ((cosjiro >> (right - 3) & 0b11111 ) == 0b0) && (tanjiro += 720 );
                   (right >= 4) && ((sinjiro >> (right - 4) & 0b11111  ^ 0b11011 ) == 0b0) && ((cosjiro >> (right - 4) & 0b11111 ) == 0b0) && (tanjiro += 720 );
                   (right >= 4) && ((sinjiro >> (right - 4) & 0b11111  ^ 0b10111 ) == 0b0) && ((cosjiro >> (right - 4) & 0b11111 ) == 0b0) && (tanjiro += 720 );
                   (right >= 4) && ((sinjiro >> (right - 4) & 0b11111  ^ 0b11101 ) == 0b0) && ((cosjiro >> (right - 4) & 0b11111 ) == 0b0) && (tanjiro += 720 );
    (left >= 2) && (right >= 3) && ((sinjiro >> (right - 3) & 0b111111 ^ 0b001100) == 0b0) && ((cosjiro >> (right - 3) & 0b111111) == 0b0) && (tanjiro += 120 );
    (left >= 2) && (right >= 3) && ((sinjiro >> (right - 3) & 0b111111 ^ 0b001010) == 0b0) && ((cosjiro >> (right - 3) & 0b111111) == 0b0) && (tanjiro += 120 );
    (left >= 1) && (right >= 4) && ((sinjiro >> (right - 4) & 0b111111 ^ 0b010100) == 0b0) && ((cosjiro >> (right - 4) & 0b111111) == 0b0) && (tanjiro += 120 );
    (left >= 3) && (right >= 2) && ((sinjiro >> (right - 2) & 0b111111 ^ 0b000100) == 0b0) && ((cosjiro >> (right - 2) & 0b111111) == 0b0) && (tanjiro += 20  );
    (left >= 2) && (right >= 3) && ((sinjiro >> (right - 3) & 0b111111 ^ 0b001000) == 0b0) && ((cosjiro >> (right - 3) & 0b111111) == 0b0) && (tanjiro += 20  );
    return tanjiro;
  }

  evaluate(karen: Array<number>, tsukihi: Array<number>, kakuya?: Function, araragi?: Function) : number {
    this.isend = false;
    let justice = 0;
    for (let i = 0; i < 15; i++) {
      for (let j = 0; j < 15; j++) {

        if ((karen[i] >> 15 - j - 1 ^ 1) & 1 && (tsukihi[i] >> 15 - j - 1 ^ 1) & 1) {
          /* 未落子 */
          if (araragi) {
            /* 启发式搜索，进行落子评估 */
            karen[i] |= 1 << 15 - j - 1;
          } else {
            /* 普通搜索，不评估未落子的 */
            continue;
          }
        } else if (karen[i] >> 15 - j - 1 & 1) {
          /* 已落子 */
          if (araragi) {
            /* 启发式搜索，不搜索已经落子的 */
            continue;
          } else {
            /* 普通评估，对已落子评估 */
          }
        } else {
          continue;
        }

        let tsukihi_bit = tsukihi[i] >> 15 - j - 1 & 1;
        /* 这一位上为 1 */
        {
          // console.log('-');
          /* - 向 8 bit */
          // console.log(karen[i].toString(2));
          let left, right, lseg, rseg, sinjiro, cosjiro;
          left = min(j, 3);
          right = min(15 - j - 1, 4);
          // console.log(i, j);
          // console.log(left, right);
          lseg = karen[i] >> 15 - j & 0b111;
          // console.log(lseg.toString(2));
          rseg = karen[i] & 0b1111 << 15 - j - 1 >> right;
          // console.log(rseg.toString(2));
          rseg = rseg >> 15 - j - right - 1;
          // console.log(rseg.toString(2));
          sinjiro = lseg << 1 | 1;
          sinjiro = sinjiro << right | rseg;
          lseg = tsukihi[i] >> 15 - j & 0b111;
          rseg = tsukihi[i] & 0b1111 << 15 - j - 1 >> right;
          rseg = rseg >> 15 - j - right - 1;
          cosjiro = lseg << 1 | tsukihi_bit;
          cosjiro = cosjiro << right | rseg;
          justice += this.slide8(sinjiro, cosjiro, left, right);
        }
        {
          // console.log('|');
          /* | 向 8 bit */
          let top, bottom, tseg, bseg, sinjiro, cosjiro;
          top = min(i, 3);
          bottom = min(15 - i - 1, 4);
          // console.log(top, bottom);
          tseg = 0; for (let k = i - top; k < i; k++) {
            tseg = tseg << 1 | (karen[k] >> 15 - j - 1 & 1);
          }
          bseg = 0; for (let k = i + 1; k <= i + bottom; k++) {
            bseg = bseg << 1 | (karen[k] >> 15 - j - 1 & 1);
          }
          sinjiro = tseg << 1 | 1;
          sinjiro = sinjiro << bottom | bseg;
          tseg = 0; for (let k = i - top; k < i; k++) {
            tseg = tseg << 1 | (tsukihi[k] >> 15 - j - 1 & 1);
          }
          bseg = 0; for (let k = i + 1; k <= i + bottom; k++) {
            bseg = bseg << 1 | (tsukihi[k] >> 15 - j - 1 & 1);
          }
          cosjiro = tseg << 1 | tsukihi_bit;
          cosjiro = cosjiro << bottom | bseg;
          justice += this.slide8(sinjiro, cosjiro, top, bottom);
        }
        {
          /* \ 向 8 bit */
          let lt, rb, ltseg, rbseg, sinjiro, cosjiro, x, y;
          lt = min(min(i, j), 3);
          rb = min(min(15 - i - 1, 15 - j - 1), 4);
          // console.log(i, j, lt, rb);
          y = i - lt; x = j - lt; ltseg = 0; for (let k = 0; k < lt; k++) {
            ltseg = ltseg << 1 | (karen[y + k] >> 15 - x - k - 1 & 1);
          }
          y = i + 1; x = j + 1; rbseg = 0; for (let k = 0; k < rb; k++) {
            // console.log(y + k, 15 - x + k - 1);
            rbseg = rbseg << 1 | (karen[y + k] >> 15 - x - k - 1 & 1);
          }
          // console.log(rbseg.toString(2));
          sinjiro = ltseg << 1 | 1;
          sinjiro = sinjiro << rb | rbseg;
          y = i - lt; x = j - lt; ltseg = 0; for (let k = 0; k < lt; k++) {
            ltseg = ltseg << 1 | (tsukihi[y + k] >> 15 - x - k - 1 & 1);
          }
          y = i + 1; x = j + 1; rbseg = 0; for (let k = 0; k < rb; k++) {
            rbseg = rbseg << 1 | (tsukihi[y + k] >> 15 - x - k - 1 & 1);
          }
          cosjiro = ltseg << 1 | tsukihi_bit;
          cosjiro = cosjiro << rb | rbseg;
          justice += this.slide8(sinjiro, cosjiro, lt, rb);
        }
        {
          /* / 向 8 bit */
          let rt, lb, rtseg, lbseg, sinjiro, cosjiro, x, y;
          rt = min(min(i, 15 - j - 1), 3);
          lb = min(min(j, 15 - i - 1), 4);
          // console.log(i, j, rt, lb);
          y = i - rt; x = j + rt; rtseg = 0; for (let k = 0; k < rt; k++) {
            rtseg = rtseg << 1 | (karen[y + k] >> 15 - x + k - 1 & 1);
          }
          y = i + 1; x = j - 1; lbseg = 0; for (let k = 0; k < lb; k++) {
            // console.log(y + k, 15 - x + k - 1);
            lbseg = lbseg << 1 | (karen[y + k] >> 15 - x + k - 1 & 1);
          }
          sinjiro = rtseg << 1 | 1;
          sinjiro = sinjiro << lb | lbseg;
          y = i - rt; x = j + rt; rtseg = 0; for (let k = 0; k < rt; k++) {
            rtseg = rtseg << 1 | (tsukihi[y + k] >> 15 - x + k - 1 & 1);
          }
          y = i + 1; x = j - 1; lbseg = 0; for (let k = 0; k < lb; k++) {
            lbseg = lbseg << 1 | (tsukihi[y + k] >> 15 - x + k - 1 & 1);
          }
          cosjiro = rtseg << 1 | tsukihi_bit;
          cosjiro = cosjiro << lb | lbseg;
          justice += this.slide8(sinjiro, cosjiro, rt, lb);
        }

        /* 启发式存储 */
        if (araragi) {
          // console.log(karen, tsukihi);
          karen[i] ^= 1 << 15 - j - 1;
          // console.log(karen, tsukihi);
          // console.log(justice);
          araragi(j, i, justice);
          justice = 0;
        }

      }
    }

    /* 预留接口 */
    if (kakuya) { kakuya(justice); }

    return justice;
  }
}

class Board {
  computer: Array<number>;
  human: Array<number>;
  /* araragi: Array<number>; */
  cache: Map<number, number>;
  zobirst: Zobrist;

  constructor() {
    this.computer = new Array<number>();
    this.human = new Array<number>();
    for (let i = 0; i < 15; i++) {
      this.computer.push(0);
      this.human.push(0);
    }
    this.cache = new Map<number, number>();
    this.zobirst = new Zobrist();
  }

  put (x: number, y: number, role: Role) {
    /* 落子 */
    if (role == Role.COMPUTER) {
      this.computer[y] = this.computer[y] | 1 << 15 - x - 1;
      // console.log(this.computer);
    } else if (role == Role.HUMAN) {
      this.human[y] = this.human[y] | 1 << 15 - x  - 1;
    }
  }

  take(x: number, y: number, role: Role) {
    /* 提子 */
    if (role == Role.COMPUTER) {
      this.computer[y] = this.computer[y] & ((1 << 16) - 1 - (1 << 15 - x - 1));
    } else if (role == Role.HUMAN) {
      this.human[y] = this.human[y] & ((1 << 16) - 1 - (1 << 15 - x - 1));
    }
  }
}

class AlhpaBeta {
  board: Board;
  boogiepop: Evaluate;
  depth: number;
  next: ToolMan;
  toolmen: Array<ToolMan>;

  constructor() {
    this.board = new Board();
    this.boogiepop = new Evaluate();
    this.depth = 3;
    this.next = this.genOpen26();
    this.toolmen = new Array<ToolMan>();
  }

  genOpen26() : ToolMan {
    return new ToolMan(7, 7, 0);
  }

  evaluate(depth: number) : number {
    /* 全局评分 */
    let revolution = 0;
    if (this.board.cache.has(this.board.zobirst.code)) {
      let ret = this.board.cache.get(this.board.zobirst.code);
      if (ret) return ret;
    }
    if (depth % 2 == this.depth % 2) {
      revolution = this.boogiepop.evaluate(this.board.computer, this.board.human);
    } else {
      revolution = this.boogiepop.evaluate(this.board.human, this.board.computer);
    }
    this.board.cache.set(this.board.zobirst.code, revolution);
    return revolution;
  }

  generateLegalMoves(depth: number) {
    const toolmen = new Array<ToolMan>();
    // 启发性搜索
    if (depth % 2 == this.depth % 2) {
      // console.log('电脑手');
      this.boogiepop.evaluate(this.board.computer, this.board.human, undefined, (x: number, y: number, z: number) => {toolmen.push(new ToolMan(x, y, z));});
    } else {
      // console.log('人手');
      this.boogiepop.evaluate(this.board.human, this.board.computer, undefined, (x: number, y: number, z: number) => {toolmen.push(new ToolMan(x, y, z));});
    }
    // 高值在前
    toolmen.sort((a: ToolMan, b: ToolMan) => b.z - a.z);
    return toolmen;
  }

  makeNextMove(pck: ToolMan, depth: number) {
    // console.log(pck.x, pck.y);
    if (depth % 2 == this.depth % 2) {
      this.board.put(pck.x, pck.y, Role.COMPUTER);
      this.board.zobirst.go(pck.x, pck.y, Role.COMPUTER);
    } else {
      this.board.put(pck.x, pck.y, Role.HUMAN);
      this.board.zobirst.go(pck.x, pck.y, Role.HUMAN);
    }
  }

  unMakeMove(pck: ToolMan, depth: number) {
    if (depth % 2 == this.depth %2) {
      this.board.take(pck.x, pck.y, Role.COMPUTER);
      this.board.zobirst.go(pck.x, pck.y, Role.COMPUTER);
    } else {
      this.board.take(pck.x, pck.y, Role.HUMAN);
      this.board.zobirst.go(pck.x, pck.y, Role.HUMAN);
    }
  }

  alphaBeta(depth: number, alpha: number, beta: number) : number {
    // console.log('depth' + depth);
    // console.log(depth, alpha, beta);
    if (depth == 0) {
      // console.log('depth = 0');
      // console.log(this.evaluate(depth));
      return this.evaluate(depth);
    }
    const toolmen : Array<ToolMan> = this.generateLegalMoves(depth);
    if (toolmen.length > 0) {
      this.next = toolmen[0];
    }
    // console.log(toolmen);
    // console.log(toolmen);
    for (let i = 0; i < toolmen.length; i++) {
      // console.log('makeNextMove');
      this.makeNextMove(toolmen[i], depth);
      // console.log(depth);
      let val = -this.alphaBeta(depth - 1, -beta, -alpha);
      // console.log('val: ' + val);
      // console.log(depth);
      // console.log(depth - 1 + ':' + val);
      this.unMakeMove(toolmen[i], depth);
      if (val > beta) {
        // console.log('beta cut', val, beta);
        return beta; // 极小值冗余，不再搜索，剪掉剪掉
      }
      // alpha = max(alpha, val);
      if (val > alpha) {
        alpha = val;
        if (depth == this.depth) {
          // console.log('世界线变动')
          // console.log(toolmen[i]);
          // console.log(this.board);
          this.next = toolmen[i];
        }
      }
    }
    // console.log('last: ' + alpha);
    return alpha;
  }
}

// console.log('create memo');
(window as any).alphaBeta = new AlhpaBeta();

// export {
//   AlhpaBeta, Evaluate, Role, Zobrist, ToolMan
// };